Field of the Invention
The present invention relates generally to half-toning of images, and, more particularly, to a method and apparatus for producing halftone images using green-noise masks having adjustable coarseness.
Description of the Related Art
Many color printing devices produce color output by printing dots of different colored inks. In these instances, each pixel of a color image is represented by a color vector which is typically a CMYK (cyan, magenta, yellow, black) quadruplet. Each element within the vector is referred to as a color component in the CMYK color vector. It is sometimes convenient to consider a color image, such as a CMYK image, as the overlapping of gray-scale images where there is one gray-scale image for any one, some or all color components, and the gray-scale image for any one particular color component is the amount of that color and not necessarily the amount of black within the original color image.
Most commercial devices such as, laser printers, ink-jet printers and facsimile machines, are, with respect to any particular color component, binary-level, that is, capable of printing or not printing dots of ink. Typically, such devices are incapable of reproducing gray-scale images with respect to any particular color component. In order to reproduce gray-scale images, with respect to any particular color component, having a multitude of gray-scale values, these devices must convert the gray-scale images to binary images having only two gray-scale levels, the color component or white. The conversion must be such that the overlapping resultant binary image, when viewed by the human eye, appears to have several gray-scale values, with respect to each color component, when in fact it is just a combination of that color and white dots. Methods to convert gray-scale images to binary images for printing are referred to as xe2x80x9chalftoning.xe2x80x9d As used herein, the term xe2x80x9cgray-scale imagexe2x80x9d refers to the gray-scale image of a color image such as a CMYK image, as well as a black and white image.
Halftoning renders the illusion of various shades of gray by using only two levels, black and white, and can be implemented either digitally or optically. In the case of digital halftoning, points correspond to pixels. Many digital halftoning methods exist in practice today. Clustered-dot dithering, which is similar to the analog method used to render images in newspapers, and error diffusion are two such methods. The method known as halftoning via xe2x80x9cblue-noise masks,xe2x80x9d however, is the preferred method used in the reproduction industry due to its simplicity and performance. As referred to herein, the term xe2x80x9cblue-noisexe2x80x9d is a pattern having predominantly high frequency components of white noise and which possesses certain visually pleasing properties, as described in U.S. Pat. No. 5,111,310 to Parker et al. Other halftoning methods of similar complexity to blue-noise masks produce significantly inferior halftone images.
The concept of blue-noise and its associated spectral characteristics have had a profound impact in digital printing technology. R. Ulichney, in xe2x80x9cDithering With Blue-noise,xe2x80x9d Proceeding Of The IEEE, January 1988, first observed that the spectral characteristics of homogeneous binary patterns created by error diffusing constant gray signals, closely follow the spectral characteristics of blue-noise and its high-frequency components. Ulichney studied the one-dimensional radially averaged power spectrum density (RAPSD) of a blue-noise binary pattern of a given gray-level g. The cut-off frequency f6, also known as the principle frequency, determines the average distance between the minority pixels of a binary blue-noise pattern. Principle frequency f6 depends on the gray-level and is expressed as:                               f          b                =                                                                                                  g                                    R                                ,                                                      for                    ⁢                                          xe2x80x83                                        ⁢                    0                                     less than                   g                  ≤                  0.5                                                                                                                                                                    1                      -                      g                                                        R                                ,                                                      for                    ⁢                                          xe2x80x83                                        ⁢                    0.5                                     less than                   g                  ≤                  1.0                                                                                        (        1        )            
where R is the minimum distance between addressable points in the display. An additional measure utilized for analyzing binary dither patterns consists of the pair correlation defined by D. Stoyan, W. S. Kendall, and J. Mecke in Stochiastic Geometry and Its Applications, (John Wiley and Sons, New York, 1987) [hereinafter referred to as xe2x80x9cStoyan et al.xe2x80x9d]. As defined by Stoyan et al., a point process "PHgr" is a stochastic model governing the location of points xi within the space R2, where R2 is the two-dimensional real space. A sample xcfx86 of the point process "PHgr" is written as xcfx86={xixcex5R2: i=1, . . . , N}, and a scalar quantity xcfx86(B) is defined as the number of points xi in the subset B of R2. It is assumed that the point process xcfx86 is simple, meaning that ixe2x89xa0j implies xixe2x89xa0xj, which further implies:                                           lim            ⁢                          xe2x80x83                        ⁢                          φ              ⁡                              (                                  dV                  x                                )                                                                        dV              x                        →            0                          =                  {                                                                                          1                    ⁢                                          xe2x80x83                                        ⁢                    for                    ⁢                                          xe2x80x83                                        ⁢                    x                                    ∈                  φ                                                                                                      0                  ⁢                                      xe2x80x83                                    ⁢                  else                                                                                        (        2        )            
where dVx is the infinitesimally small area around x. In terms of a discrete dither pattern, sample xcfx86 represents the set of minority pixels such that xcfx86[n]=1 indicates a minority pixel at location n. A minority pixel is a pixel which is xe2x80x9conxe2x80x9d while more than half of all pixels are xe2x80x9coff,xe2x80x9d and which is xe2x80x9coffxe2x80x9d when more than half of all pixels are xe2x80x9con.xe2x80x9d A pixel is deemed to be turned xe2x80x9conxe2x80x9d when the pixel has a smaller value than a predetermined gray level g value. A pixel is deemed to be turned xe2x80x9coffxe2x80x9d when the pixel has a larger value than the predetermined gray level g value. If exactly half of all pixels are xe2x80x9con,xe2x80x9d then either group may be treated as the minority pixels.
Given xcfx86xcex5"PHgr", a pair correlation R(r) is defined as:                               R          ⁡                      (            r            )                          =                              E            ⁡                          (                                                φ                  ⁡                                      (                                                                  R                        y                                            ⁡                                              (                        r                        )                                                              )                                                  |                                  y                  ∈                  φ                                            )                                            E            ⁡                          (                              φ                ⁡                                  (                                                            R                      y                                        ⁡                                          (                      r                      )                                                        )                                            )                                                          (        3        )            
where Ry(r) specifies the ring centered around the point yxcex5"PHgr" with an inner radius r and an outer radius r+dr, as shown in FIG. 1. In terms of a binary dither pattern, R(r) is the ratio of the average number of minority pixels located a distance d away from the minority pixel at sample y, such that rxe2x89xa6d less than r+dr, to the average number of minority pixels in a region of size Nr pixels with a gray-level g. Region size Nr is the total number or pixels located a distance d away from the minority pixel located at sample y, such that rxe2x89xa6d less than r+dr, and g is the average gray-level of the dither pattern.
As described in U.S. Pat. No. 5,111,310 issued to Parker et al., blue-noise mask halftoning, also referred to as frequency modulated (FM) screening, performs a pixel-by-pixel comparison of the gray-scale image against a halftone screen or mask having high, radially-isotropic frequency, i.e., blue-noise, characteristics. Under ideal printing conditions, blue-noise mask halftoning provides optimal rendering of gray-scale images when viewed by the human eye. However, in real printers using blue-noise mask halftoning, printed black dots are not perfect squares and neighboring pixels overlap each other causing printed images to appear darker than desired. In addition, printer distortions such as dot gain further degrade image quality. These image defects are called xe2x80x9cartifactsxe2x80x9d because they represent an artificial feature caused by the method of image creation instead of a true feature of the desired image.
A modified approach to the construction of a blue mask is reported in M. Yao and K. J. Parker, xe2x80x9cModified approach to the Construction of a blue-noise mask,xe2x80x9d Journal of Electronic Imaging, Vol. 3, January 1994. A hybrid deterministic/random approach is used in Y. Meng and K. J. Parker, xe2x80x9cDot gain compensation in the blue-noise mask,xe2x80x9d No. VI in Human Vision, Visual Processing, and Digital Display VI, (SPIE), 1995, for modification of blue-noise masks in order to compensate for the dot-gain problem present in printing hardware. Finally, a radially asymmetric FM mask (blue-noise mask) is derived using a novel optimization algorithm as noted in J. Allebach and Q. Lin, xe2x80x9cFM screen design using dbs algorithm,xe2x80x9d No. VI in International Conference on Image Processing, IEEE, 1996. However, such modified approaches to blue-noise mask construction still fail to overcome the difficulties encountered with conventional blue-noise masks.
Traditional halftoning used in printing newspaper images and some digital halftoning algorithms, in contrast to the FM halftoning, rely upon amplitude-modulated (AM) halftoning where the size of the halftone dot varies with the gray-scale of the continuous tone image. AM halftoning is more desirable than FM halftoning when the printer characteristics depart from the ideal square pixel model. However, AM halftoning is limited to small-screen, order-dithered type algorithms, leading to less effective halftoning patterns.
An object of the invention is to provide a method for producing halftone images of better quality than those obtained using blue-noise mask (FM) halftoning, while enjoying the same implementation complexity as that of blue-noise mask halftoning.
A further object of the present invention is to provide a method for producing halftone images that overcomes the limitations of blue-noise mask (FM) halftoning, such as the occurrence of unwanted artifacts.
A still further object of the present invention is to provide a method for producing halftone images which combines the maximum dispersion attributes of blue-noise mask halftoning and the clustering qualities of AM halftoning.
Additional objects and advantages of the invention will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims.
To achieve the objects and in accordance with the purpose of the invention, as embodied and broadly described herein, the invention comprises a method for producing a halftone image from a gray-scale image in a computing means, the method comprising the steps of: acquiring the gray-scale image to create a gray-scale image array on a pixel-by-pixel basis; storing the gray-scale image array in a first memory of the computing means; utilizing a pixel-by-pixel comparison of the gray-scale image against a green-noise mask array stored in a second memory of the computing means; comparing, on a pixel-by-pixel basis, the value of each corresponding pixel in the gray-scale image array to produce a binary image array; and converting the binary image array to the halftone image.
Further in accordance with the objects, the present invention comprises an apparatus for producing a halftone image from a gray-scale image, the apparatus, comprising: a data acquisition means for acquiring the gray-scale image to create a gray-scale image array on a pixel-by-pixel basis; storage means for storing the gray-scale image array in a first memory of a computing means; a green-noise mask stored in a second memory of the computing means, the green-noise mask producing a pixel-by-pixel comparison of the gray-scale image; comparing means for comparing, on a pixel-by-pixel basis, the value of each corresponding pixel in the gray-scale image array to produce a binary image array; and converting means for converting the binary image array to the halftone image.
Still further in accordance with the objects, the present invention comprises an apparatus for producing a color halftone image from a series of gray-scale images, wherein each gray-scale image corresponds to each color component of the color halftone image, the apparatus comprising: a data acquisition means for acquiring any one of the gray-scale images to create a gray-scale image array on a pixel-by-pixel basis; storage means for storing the gray-scale image array in a first memory of a computing means; a green-noise mask stored in a second memory of the computing means, the green-noise mask producing a pixel-by-pixel comparison of the gray-scale image; comparing means for comparing, on a pixel-by-pixel basis, the value of each corresponding pixel in the gray-scale image array to produce a binary image array; and converting means for converting the binary image array to the halftone image.
Also in accordance with the objects, the present invention comprises a method for producing a green-noise mask for use in a method for producing a halftone image from a gray-scale image comprised of pixels, the green-noise mask production method comprising the step of: generating a sequence of binary dot profiles under a stacking constraint, wherein pixels are turned xe2x80x9conxe2x80x9d in the dot profile of a gray level g and remain xe2x80x9conxe2x80x9d for all dot profiles corresponding to higher values of the gray level g, and the dot profile corresponding to the gray level g has a radially averaged power spectrum with little or no low frequency components, a high frequency component that diminishes with an increasing coarseness parameter Mxe2x80x2(g), and a sharp spectral peak at radial frequency fg where:       f    g    =                                                                        g                                                      M                    xe2x80x2                                    ⁡                                      (                    g                    )                                                                        R                    ,                                    for              ⁢                              xe2x80x83                            ⁢              0                         less than             g            ≤            0.5                                                                                                                    (                                      1                    -                    g                                    )                                                                      M                    xe2x80x2                                    ⁡                                      (                    g                    )                                                                        R                    ,                                    for              ⁢                              xe2x80x83                            ⁢              0.5                         less than             g            ≤            1.0                    ,                    
wherein R is the minimum distance between addressable points, Mxe2x80x2(g) is the coarseness parameter for gray level g, and the dot profile corresponding to the gray level g has a pair correlation with a non-zero value at radial distance r near zero and peaks at integer multiples of the radial distance xcexg where:       λ    g    =                                          R                                          g                                                      M                    xe2x80x2                                    ⁡                                      (                    g                    )                                                                                ,                                    for              ⁢                              xe2x80x83                            ⁢              0                         less than             g            ≤            0.5                                                                    R                                                            (                                      1                    -                    g                                    )                                                                      M                    xe2x80x2                                    ⁡                                      (                    g                    )                                                                                ,                                    for              ⁢                              xe2x80x83                            ⁢              0.5                         less than             g            ≤                          1.0              .                                          
Still further in accordance with the objects, the present invention comprises a method for producing a green-noise mask for use in a method for producing a halftone image from a gray-scale image, the green-noise mask production method comprising the step of, based upon a sequence of binary dot profiles which satisfy a stacking constraint, assigning to each element of the green-noise mask a value defined by a gray level at which a corresponding pixel in the sequence of binary dot profiles is turned xe2x80x9con.xe2x80x9d
Further in accordance with the objects, the present invention comprises a green-noise mask for use in a method for producing a halftone image from a gray-scale image, the green-noise mask comprising: an array of deterministic numerical values such that when the array is thresholded with a pixel-by-pixel comparison of the array with a gray level g such that each pixel of the resulting dot profile which corresponds to a pixel in the array which is less than g is turned xe2x80x9conxe2x80x9d and otherwise is turned xe2x80x9coff,xe2x80x9d wherein the resulting dot profile has a radially averaged power spectrum with little or no low frequency components, a high frequency component that diminishes with an increasing coarseness parameter Mxe2x80x2(g), and a sharp spectral peak at approximately the radial frequency fg where:       f    g    =                                                                        g                                                      M                    xe2x80x2                                    ⁡                                      (                    g                    )                                                                        R                    ,                                    for              ⁢                              xe2x80x83                            ⁢              0                         less than             g            ≤            0.5                                                                                                                    (                                      1                    -                    g                                    )                                                                      M                    xe2x80x2                                    ⁡                                      (                    g                    )                                                                        R                    ,                                    for              ⁢                              xe2x80x83                            ⁢              0.5                         less than             g            ≤            1.0                    ,                    
wherein R is the minimum distance between addressable points, Mxe2x80x2(g) is the coarseness parameter for gray level g, and the dot profile corresponding to the gray level g has a pair correlation with a non-zero value at radial distance r near zero and peaks at integer multiples of the radial distance xcexg where:       λ    g    =                                          R                                          g                                                      M                    xe2x80x2                                    ⁡                                      (                    g                    )                                                                                ,                                    for              ⁢                              xe2x80x83                            ⁢              0                         less than             g            ≤            0.5                                                                    R                                                            (                                      1                    -                    g                                    )                                                                      M                    xe2x80x2                                    ⁡                                      (                    g                    )                                                                                ,                                    for              ⁢                              xe2x80x83                            ⁢              0.5                         less than             g            ≤                          1.0              .                                          
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.